package pers.qianyu.month_202101.date_20210127;

import org.junit.*;

import java.util.*;


/**
 * 剑指 Offer 29. 顺时针打印矩阵
 * https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 *
 * @author mizzle rain
 * @date 2021年1月27日14:19:38
 */
public class SpiralOrder {
    // 比较麻烦的一种方法：定义边界
    public int[] spiralOrder(int[][] matrix) {
        int h = matrix.length;
        if (h == 0) return new int[0];
        int w = matrix[0].length;
        if (w == 0) return new int[0];
        int left = 0, right = w - 1, top = 0, btn = h - 1;
        List<Integer> list = new ArrayList<>();
        while (left <= right || top <= btn) {
            for (int i = left; i <= right && top <= btn; i++) {
                list.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= btn && left <= right; i++) {
                list.add(matrix[i][right]);
            }
            right--;
            for (int i = right; i >= left && top <= btn; i--) {
                list.add(matrix[btn][i]);
            }
            btn--;
            for (int i = btn; i >= top && left <= right; i--) {
                list.add(matrix[i][left]);
            }
            left++;
        }
        int size = list.size();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) arr[i] = list.get(i);
        return arr;
    }

    // 定义方向，直到不能走的时候换方向
    public int[] spiralOrder2(int[][] matrix) {
        int h = matrix.length;
        if (h == 0) return new int[0];
        int w = matrix[0].length;
        if (w == 0) return new int[0];
        boolean[][] visited = new boolean[h][w];
        int[][] dxy = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int[] res = new int[h * w];
        int d = 0, x = 0, y = 0, index = 0;
        for (int i = 0; i < h * w; i++) {
            res[index++] = matrix[x][y];
            visited[x][y] = true;
            int a = x + dxy[d][0], b = y + dxy[d][1];
            if (a < 0 || b < 0 || a >= h || b >= w || visited[a][b]) {
                d = (d + 1) % 4;
                a = x + dxy[d][0];
                b = y + dxy[d][1];
            }
            x = a;
            y = b;
        }
        return res;
    }

    @Test
    public void test0() {
        int[][] param = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        int[] result = new SpiralOrder().spiralOrder(param);
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test1() {
        int[][] param = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16},
                {17, 18, 19, 20}
        };
        int[] result = new SpiralOrder().spiralOrder(param);
        System.out.println("result = " + Arrays.toString(result));
        Assert.assertArrayEquals(result, new int[]{1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5, 6, 7, 11, 15, 14, 10});
    }
}